Two-Sided Malicious Security for Private Intersection-Sum with Cardinality
具有基数的隐私交集求和的两方恶意安全
具有基数的（cardinality）隐私交集求和允许两方，其中每方持有一个隐私集合，其中一方还持有与它的集合中的每个元素相关的隐私整数值，共同计算两个集合的相交的基数，以及相交中所有元素的相关整数值的总和，除此之外没有其他。
我们提出了一种新的隐私交集求和的构造，它提供了带有中止功能的恶意安全，并保证双方在成功完成协议后都能收到输出。我们构造的一个核心构件是一个称为洗牌分布式不经意伪随机函数（DOPRF）的基元，它是一个伪随机函数（PRF），使用双方共享的密匙提供不经意评估，此外还允许不经意地混合几个平行不经意评估的 PRF 输出。我们提出了第一个具有恶意安全的洗牌 DOPRF 的构造。我们进一步提出了几个新的 sigma 证明协议，用于跨 Pedersen 承诺、ElGamal 加密和 Camenisch-Shoup 加密的关系，我们在主要构造中使用了这些协议，为此我们开发了新的批处理技术以减少通信。
我们实现并评估了我们协议的效率，并表明我们可以实现通信成本只比最有效的半诚实协议大 4-5 倍。当测量在云中执行协议的货币成本时，我们的协议比半诚实协议的成本高 25 倍。我们的结构还允许不同的参数制度，使通信和计算之间的权衡成为可能。
1. 介绍
隐私集合求交集：隐私集合求交集（PSI）协议使两方都有一个隐私的输入集，可以计算两个集的交集，而除了交集本身外，不能获得其他的信息。尽管功能简单，PSI 在隐私保护的位置共享 [NTL+11]、全测序人类基因组测试 [BBDC+11]、协作僵尸网络检测 [NMH+10]、数据挖掘 [ARF+10]、社交网络 [LCYL11, NDCD+13]、在线游戏 [BHLB11]、测量广告转换率 [IKN+17] 等方面发现许多应用。由于它的重要性和广泛的应用，PSI 已经在一长串的工作中被广泛研究 [HFH99, FNP04, DSMRY09, DCKT10, HEK12, DCW13, SFF14, PSZ14, PSSZ15, EFG+15, DD15, Lam16, KKRT16, RR17a, RR17b, FNO18, PSWW18, PRTY19] 。
增强功能：虽然 PSI 功能成功地模拟了一些应用场景中的保密性要求，但在一些信息共享环境中，揭示整个交集是不可接受的，而是需要一个更细粒度的隐私保护计算。特别是对相交集的不同聚合计算为广泛的应用提供了限制隐私泄露的模型。具有基数的 PSI 是这种聚合功能的一个例子，它限制双方只学习交集的基数（或大小）[HFH99, AES03, FNP04, KS05, VC05, NAA+09, DCGT12]。
Ion 等人 [IKN+17] 引入的隐私交集求和功能是聚合功能的另一个例子，其中一个输入集有与该集的元素相关的整数值，双方计算相交的基数，以及与相交集相关的整数值的聚合。这种原始方法模拟了实践中的许多应用。其中包括这样的设置：一方持有关于一组人的隐私统计资料，另一方拥有关于这组人的成员资格的信息，而这两方想要计算关于这组成员的统计资料的集合。Nagu 等人 [NDCD+13] 在社交网络的背景下考虑了这种情况的一个具体实例，即一个用户知道与她的每个朋友相关的权重，并想计算她与另一个用户共同拥有的朋友的总（或平均）权重。在测量广告转化率时 [IKN+17]，广告商可能知道每个客户的购买金额，广告商和广告发布者可以共同计算从发布者那里看到广告并最终购买产品的客户总数和总购买金额。
现有的隐私相交和的解决方案 [IKN+17] 只在半诚实的情况下提供安全性，即假设每一方都诚实地遵守协议。虽然在互动各方有外部激励（例如法律协议）来遵循协议的情况下，这种安全水平可能是足够的，但对于对手可能任意偏离协议的广泛场景，这种安全水平是不够的。在恶意安全的设置中，我们有只实现 PSI 功能的协议，然而，具有竞争效率的构造 [FHNP16, RR17a, RR17b] 有一个主要的缺陷，即它们只支持单边输出，在许多设置中，双方都需要获得计算的输出。升级这些协议以实现双面输出是一项非同小可的任务。例如，正如 Rindal 等人 [RR17b] 所解释的，单边协议的输出接受者需要证明它诚实地执行了协议的最后一步。我们没有为这一任务量身定做的结构，而且应用通用的方法会有很高的代价。
在这项工作中，我们考虑了恶意环境中的隐私交集求和的问题，它提供了对这种对抗者的保护。我们要求双方要么收到计算的输出，要么放弃。我们的重点是优化协议的通信效率，因为正如 Ion 等人 [IKN+17] 的工作中所讨论的，这是实践中最重要的成本。
我们的贡献：我们提出了一个新的具有基数的隐私交集求和协议，该协议实现了带有中止的恶意安全，这保证了如果协议没有中止，双方都能收到相交和。我们的协议提供了双面输出，即使我们把注意力只限制在 PSI 功能上，这已经是一种改进，因为现有的恶意 PSI 协议 [FHNP16, RR17a, RR17b] 被限制在单一输出接收者上。
我们的构造是第一个具有恶意安全的隐私交集求和的构造，在集合的大小
我们的结构也可以被实例化，使实现恶意安全比半诚实版本所需的开销需要亚线性的
我们的构造采用了 Ion 等人 [IKN+17] 的工作中的一般方法，该方法利用带有共享密钥的不经意伪随机函数（PRF），它可以以分布式的方式进行评估，将输入集的值置换并映射到一个伪随机空间，从而实现交集的计算，同态加密允许在 PRF 评估期间配对相关的值，然后评估交集的和。为了将这一通用方法升级为恶意安全，我们开发了几项新技术，这些技术可能具有独立的利益：
新的分布式 OPRF：我们解决方案的一个核心构件是一个具有恶意安全的分布式 OPRF。为了实现具有恶意安全的分布式 OPRF，我们利用了 Dodis 和 Yampolskiy [DY05] 的 PRF 构造，对于该构造，我们可以构造关于承诺的 PRF 密钥的诚实评估证明。我们需要处理的一个问题是，这个 PRF 被证明只对多项式域安全。为了规避这个问题，我们为 PRF 引入了一个较弱的选择性安全概念，这个概念被指数域的构造所满足，并且我们表明这个属性对于我们的具有基数的隐私交集求和协议是足够的。
可验证的参数生成：我们构建了一个分布式的 PRF 评估协议，该协议对承诺的和加密的值进行了多次评估。因此，为了实现该协议的恶意安全，我们使用加密值和承诺值之间的关系证明，这关键是依赖于这些方案的参数是诚实生成的假设。由于我们不想假设任何可信的设置，我们提出了可验证的 Pedersen 承诺、Camenish-Shoup（CS）和 ElGamal 加密的参数生成协议。
松弛的范围证明：分布式 OPRF 的最后一个扩展是实现对平行执行的多个输入的不经意评估的洗牌，这隐藏了与原始输入的映射，并且是为了隐藏交集中的元素而需要的。为了实现这一点，我们开发了一个关于 Camenisch-Shoup 加密的洗牌解密的证明协议。我们利用 Bayer-Groth 洗牌证明 [BG12]，它可以证明两组密码对同一组明文进行加密，直至发生变化。为了能够在这一步中证明指数的知识，证明者需要从 Camenisch-Shoup 加密转换到 ElGamal 加密，它们有不同的领域。我们介绍了一种证明技术，用于证明在 CS 和 ElGamal 加密下加密的数值的一致性，该技术使用带有松弛的范围证明。
我们的构造在几个地方大量利用了 sigma 证明协议 [Dam02]，包括 DOPRF 的评估证明，洗牌的重新加密步骤，交叉和的重新随机化。
范围证明的批处理：我们介绍了基于 sigma 协议的范围证明的新批处理技术。现有的高效批处理证明并不与数值的位级表示法一起工作，而是在未知顺序的组中运行 [Bou00,CS03]，而 sigma 协议的批处理技术只在已知顺序组的情况下构建 [GLSY04]。我们展示了如何在未知顺序的组上进行批量范围证明，同时避免范围证明的松弛度出现大的爆炸，如果我们直接将已知组顺序的批处理方法适应于隐藏顺序，就会产生足够的空间来避免模数减少的需要。
CS 和 ElGamal 加密的批处理证明：我们还将批处理技术用于承诺，并为 Camenisch-Shoup 加密开发批处理方法。我们以一种新的方式利用 Bayer 和 Groth [BG12] 的工作中的多重指数论证，对验证者不知道加密随机性的 ElGamal 密文之间的关系进行批量证明。由于我们需要一个具有可证明的阈值解密的加法同态加密方案，我们使用指数 ElGamal 来加密关联值。这意味着我们的结构支持评估，对于这些评估，最终的相交和是在一个多项式域内，可以计算离散对数来进行解密。
实施和评估：我们实现了我们的恶意安全隐私交集求和协议，并在大规模数据集上评估了其性能。我们的实验表明，当我们设置参数以最小化通信开销时，我们的协议的通信成本大约比基于 DDH 的最有通信效率的半诚实协议高 4 倍。不太激进的参数选择导致比基于 DDH 的半诚实协议扩大了约 7 倍，计算效率也有很大提高。我们还使用谷歌云的定价估计了运行我们协议的货币成本，并得到在大小为
相关工作：在介绍我们的构造的技术概况之前，我们先概述一下恶意设置中现有的 PSI 解决方案 [KS05, HL08, DSMRY09, CZ09, CKRS09, JL09, HN10, DCKT10, FHNP16, RR17a, RR17b]，并讨论将这些工作中的方法扩展到隐私交集求和问题的挑战。由于我们的主要目标是通信效率，我们将讨论限制在提供线性通信复杂性的构造上。
De Cristofaro 等人的工作 [DCKT10] 提出了一个 PSI 协议，其中只有一方（
Jarecki 和 Liu [JL09] 的 PSI 协议也是基于与上述类似的 OPRF 协议，但双方可以证明他们对 OPRF 的输入与之前承诺的值的一致性。因此，双方可以先承诺他们的输入，然后在两个方向上运行上述协议，这样双方都能学到 PSI 的输出。然而，该协议有一些局限性。首先，他们的安全证明需要将元素的域限制为安全参数的多项式。此外，该协议需要一个通用参考字符串（CRS），其中 CRS 包括一个安全的 RSA 模数，必须由受信任的第三方生成，这是我们想避免的。为了将这个协议扩展到具有基数的隐私集合求交，OPRF 协议的接收方（
Freedman 等人 [FHNP16] 的协议中实现恶意安全的想法是要求一方（
构建具有恶意安全的隐私交集求和协议的另一个选择是将直接恶意的两方计算协议应用于我们的功能。这种协议使用被评估功能的电路表示。计算两个大小为
2. 技术概述
在这一节中，我们给出了我们的恶意安全隐私交集求和协议的技术概述。我们的出发点是半诚实的私有相交和协议 [39]。我们确定了从半诚实的版本中获得恶意安全的技术挑战，然后介绍了我们解决这些问题的方法。
半诚实的隐私交集求和：Ion 等人 [39] 的半诚实协议利用了一种被称为分布式不经意伪随机函数（DOPRF）的加密基元，它可以实现以下功能。DOPRF 的密钥 k 在两方之间共享，其中每一方都可以独立生成他们的份额。DOPRF 有一个不经意评估功能，这是一个 2 方计算协议，双方共同评估 PRF
DOPRF 功能足以构建一个 PSI 协议，具体如下。首先，双方独立生成 DOPRF 密钥的密钥共享。然后，他们使用不经意评估协议来评估
上述 PSI 协议可以扩展到获得 PSI-cardinality 和私有相交和协议。为了实现 PSI-cardinality，只需构建一个洗牌的 DOPRF 协议，该协议允许
上面描述的基元和协议只对半诚实的对手是安全的。为了构建一个提供恶意安全的私有相交和协议，我们设计了这些工具的恶意对应物。
恶意的 DOPRF：Ion 等人 [39] 的半诚实交叉和协议使用以下基于 Diffie-Hellman 的 PRF 构造，其定义为
鉴于上述与在恶意设置中使用基于 DH 的 DOPRF 有关的困难，我们选择使用一个不同的 PRF 作为新的 DOPRF 构造的起点，对它的正确评价可以被证明。我们使用函数
我们首先描述了上述 PRF 的分布式评估协议，它提供了半诚实的安全性。我们把双方称为发送方和接收方，其中持有输入
在上述协议中，接收方学到了 PRF 输出之外的信息，其中包括值
为了获得上述协议中的恶意安全，发送方需要证明同态加密的正确性，以及
Dodis-Yampolskiy PRF 的指数域：Dodis 和 Yampolsky 的工作 [23] 证明了我们上面讨论的 PRF 构造的自适应安全性，但只是在多项式大小的域的设置中。然而，对于许多现实世界的应用中使用的输入来说，这是不正确的。因此，我们重新审视了这个结构的安全证明，并表明对于指数大小的域，PRF 满足较弱的选择性安全概念，在 q-DHI 假设下，PRF 的输入是由对手在安全游戏中预先选择的。此外，由于以下原因，PRF 的这种安全水平对于我们的私有相交和协议的安全是足够的。在高层次上，我们让双方首先承诺自己的输入，同时进行零知识证明，然后共同决定 PRF 参数。在基于模拟的证明中，模拟器可以首先提取对手的输入，然后还原为 PRF 的安全博弈，其中的选择性安全足以满足我们的目的。
恶意的 PSI：正如我们为半诚实环境所讨论的，安全的 DOPRF 协议足以满足 PSI 协议的要求。在恶意设置中，为了从上述恶意 DOPRF 协议中构建一个恶意 PSI 协议，接收方应该将 PRF 值发回给发送方，并以零知识的方式证明其计算
恶意洗牌的 DOPRF：为了将恶意 PSI 协议扩展到恶意 PSI-cardinality，我们需要额外启用洗牌 DOPRF 功能，以接收方决定的随机洗牌（permuted）顺序向发送方提供所有 PRF 输出。虽然我们的恶意 DOPRF 协议为接收方提供了在发回给发送方之前对 PRF 输出进行洗牌的杠杆，但我们仍然需要一种方法来证明洗牌的正确性。
虽然可以尝试利用通用的零知识协议来直接证明洗牌输出的正确性，但我们选择使用 Bayer-Groth 的 shuffle-decrypt 协议 [5]，它可以有效地在零知识中证明，给定一组密码文和一组明文，明文对应于密码文的一些排列组合的解密。为了在我们的协议中加入这种洗牌证明，接收方不再只是在 DOPRF 评估后将 PRF 输出发回给发送方，而是将这些输出的加密与证明一起发送，证明每一个输出都加密了正确计算的值
在我们为了利用有效的洗牌证明而设计的上述结构中，让
从洗牌 DOPRF 到交集和：洗牌 DOPRF 协议足以在半诚实的环境下获得 PSI-cardinality，方法是用相同的密钥运行两个洗牌 DOPRF，其中一个协议中
为了进一步实现隐私交集求和，类似于半诚实的设置，我们使用加法同态加密法对与其中一个集合相关的整数值进行加密。这种加密的秘密密钥现在在双方之间共享，这对保持洗牌证明的保密性保证很重要。发送方将这些加密附加到恶意洗牌的 DOPRF 评估中的相应输入。现在，在该协议中应用洗牌的接收方还需要重新随机化相关值的加密，并提供一个证明，即应用于这些加密的洗牌与 PRF 值上的洗牌是一样的。这可以在 Bayer-Groth 洗牌证明中实现，因为在他们的协议中，验证人承诺了洗牌，我们可以通过两个洗牌证明使用相同的承诺。与半诚实的设置不同，现在双方都可以计算两组 PRF 值的交集，并同态地增加相应的重新随机化的密文。为了共同解密所产生的密文，每一方都使用自己的密钥份额对密文进行部分解密并发送给另一方。他们还必须证明其部分解密的正确性，同样通过西格玛协议。
分批协议组件：在我们上述的构造中，我们使用西格玛风格的协议来为 DOPRF 评估的正确性提供证明，为洗牌重新加密，为交叉和重新随机化。为了优化这种协议的通信效率，我们利用各种技术对协议的组成部分进行批处理。在高层次上，我们使用的批处理有三种类型：批处理 Pedersen 承诺，批处理 CamenischShoup 加密，以及批处理 sigma 协议。
这些批处理技术将在第 5 节描述。需要进一步注意的是，确保不同批处理技术之间的兼容性。我们在论文的完整版本中描述了这些技术的详细构成。
我们认为，这些批处理技术可能具有独立的意义。例如，我们的分批西格玛协议包括比已知技术更严格的范围证明，我们的分批 Camenisch-Shoup 加密实现了分批的解密证明，这带来了渐进的效率提升。
组织：我们在第 3 节中介绍了我们的符号、安全假设、重要定义和加密方案，并在第 4 节中介绍了我们的私有相交和协议。我们的批处理技术在第 5 节中描述。 关于我们协议的详细恶意安全证明，具体的西格玛协议，以及我们协议中使用的 PRF 的选择性安全证明，请参阅我们论文的完整版本 [46]。
3. 预备工作
3.1 符号
我们用
3.2 计算假设
决策性 q-Diffie-Hellman 反演（q-DHI）假设 [47]。在群
3.3 密码学工具
我们在这一节中介绍一些加密工具。关于 Pedersen 承诺 [53]、Camenisch-Shoup 加密 [13]、ElGamal 加密 [26] 和 2-out-of-2 阈值加密的描述，请参见本文的完整版本。
零知识的知识论证。我们使用 [14] 中介绍的符号来表示离散对数知识的各种零知识论证和关于离散对数的语句的有效性论证。下面的例子是逐字逐句摘自 [13]。
我们对零知识证明使用类似的符号。作为一个例子、
在我们的协议中，我们通过西格玛协议实例化了这种形式的零知识论证和零知识证明。我们在第 5 节中阐述了如何做到这一点，以及批处理技术对西格玛协议的作用。在我们的构造中使用的具体西格玛协议将在我们的完整版本中介绍。
Fiat-Shamir 启发法。所有的西格玛协议都是交互式的，并且是公共币，其中来自验证者的信息都是统一随机选择的，与验证者发送的信息无关。我们只证明它们是诚实验证人的零知识。通过 Fiat-Shamir 启发式 [29]，这些协议可以变成一个非交互式的证明或论证，其中验证人用加密哈希函数计算公共币的挑战，而不是与验证人互动，这减少了通信回合以及总通信成本。此外，由此产生的非交互式协议可以被证明在随机神谕模型中是恶意安全的。
洗牌证明。Bayer-Groth [5] 提出了一种针对同态加密的重新随机化和洗牌的正确性的零知识知识证明，其实现了亚线性的通信复杂性。具体而言，给定同态加密的公钥
3.4 安全模型
我们在理想 / 现实世界的范式中定义了隐私交集求和协议对恶意对手的安全性。该定义将现实世界的执行结果与涉及受信任的第三方的理想世界的执行结果进行比较，我们称之为理想功能。图 1 中定义的理想功能
从形式上讲，如果对于现实世界中的每一个 PPT 对手
图 1. 恶意安全隐私交集求和的理想功能。
4 协议描述
我们的结构由两个阶段组成。第一个阶段是离线设置，双方共同决定加密基元的参数，这些参数将在在线计算中使用。请注意，我们不假设任何基元的可信设置，并为这些基元提供安全的两方计算协议。第二阶段是在线计算，它依赖于输入集并使用设置的参数。我们在线阶段的主要构件是一个洗牌的分布式 OPRF（DOPRF）结构，它是一个具有独立兴趣和其他潜在应用的基元。因此，我们单独介绍洗牌的 DOPRF 构造。
离线设置。在我们的恶意安全隐私交集求和协议中，双方首先运行一个（一次性的）离线设置，以生成加密和承诺方案的参数。双方首先商定一个群
在线阶段。在一次性离线设置后，对于每个隐私交集求和实例，双方运行图 3 中描述的在线协议。两方的输入如下：
在高层次上，该协议使用洗牌 DOPRF，使双方都能获得
洗牌 DOPRF 协议：我们在图 4 中把我们的恶意安全洗牌 DOPRF 构造作为一个独立的基元来描述。在下面的讨论中，
此外，在对
启用批处理：到目前为止，我们描述了我们对每个元素
在在线阶段的第 2 步，
为了使批处理 Camenisch-Shoup 密码文的第一部分，每个批处理的 Camenisch-Shoup 密码文有
最后，在 DOPRF 协议的第 2 轮中，
图 2. 恶意安全私人相交和协议的一次性离线设置。
图 3. 恶意安全私人相交和协议的在线阶段。
图 4. 恶意安全洗牌的 DOPRF 协议，其中
5 批处理技术
在这一节中，我们讨论了我们协议中各个部分的批处理技术。这些技术对我们协议的通信成本有很大的影响，可能会有独立的兴趣。